LeetCode是一個求職者經常會使用的線上解題系統,LeetCode網站中的Study Plan提供了求職者經過主題分類後的題目整理,本次的主題就是Study Plan中的LeetCode 75。
LeetCode 75來源於Blind 75,Blind 75是由Facebook工程師 Yangshun 所發表的一組包含75道LeetCode題目的清單,最初發表於 Blind 社群,所以被很多人稱為:Blind 75,由於它幾乎涵蓋了演算法及資料結構中常見的知識點,非常適合想要快速掌握面試知識時拿來練習。
個人猜想LeetCode以Blind 75的題目為基礎設計了LeetCode 75,兩者題目選擇相似但並非完全相同,LeetCode 75是一個有三個等級(Level 1、Level 2及Level 3)的學習計畫(Study Plan),讓使用者每天進行2-3題;今年鐵人賽希望記錄用C語言走過LeetCode 75 Level 1的題目總共是30題 (20題Easy及10題Medium)。
除了身為一個每天用C語言的韌體工程師以外,如果查詢網路上的解題資料,解答常常是以C++、Java或Python寫成,這些語言都有許多的容器和內建函數可以使用,用C語言沒有這些東西就會多了點自己造輪子的成就感。
每天會以LeetCode 75 Level 1中的一個題目作為對象,會針對題目做解釋和說明個人的想法、嘗試過的方向、經歷的錯誤等等,最後提供可通過的C語言程式碼。過程中也會參考網路上已有的解法,部分題目由於過於簡單導致篇幅會比較短,這時候就會從Level 2相同知識領域中拿一題來進行說明,所以每天會解答至少是一題至多是二題。
哈囉哈囉,大家好!我是Eric,一個韌體工程師,工作內容是撰寫車輛子系統的控制程式還有進行測試。
若系列文章中有錯字、寫錯或是有任何想討論的地方,請不吝留言告訴我!
由於計畫是30天進行30+題,所以第一天就要開始了!!
Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).
Return the running sum of nums.
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* runningSum(int* nums, int numsSize, int* returnSize){
}
本題是 Day 1 Prefix Sum 中的第一題,主題都是輸入一個陣列,然後回傳計算好的值或是另一個陣列,這題非常容易,但是若是一開始接觸時,會不太了解題目中C語言預設函數的設定,後續題目也常常會遇到要處理陣列的輸入和輸出,以下進行說明:
接下來由題目的敘述知道,我們只要把輸入陣列的第[i]項和第[i]項之前的值都加起來成為輸出陣列的第[i]項,如圖Fig. 2所示,輸出的第[i]項還可以寫成輸出的第[i - 1]項加上輸入的第[i]項。
int* runningSum(int* nums, int numsSize, int* returnSize){
int sum = 0;
int* dynArr = (int *)malloc(numsSize * sizeof(int));
*dynArr = *nums;
for (int i=1; i<numsSize; i++) {
*(dynArr+i) = *(nums+i) + *(dynArr+i-1);
}
*returnSize = numsSize; // 要回傳陣列的大小,和輸入陣列的大小相同
return dynArr;
}
第一天就到這邊結束,謝謝大家。